0962. 最大宽度坡【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 单调栈

1. 📝 题目描述

• leetcode

给定一个整数数组 A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。

找出 A 中的坡的最大宽度，如果不存在，返回 0。

---

示例 1：

输入：[6,0,8,2,1,5]
输出：4

解释：
最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.

---

示例 2：

输入：[9,8,1,0,1,9,4,0,4,1]
输出：7

解释：
最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1.

---

提示：

1. 2 <= A.length <= 50000
2. 0 <= A[i] <= 50000

2. 🎯 s.1 - 单调栈

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxWidthRamp = function (nums) {
  const n = nums.length
  const stack = [] // 单调递减栈，存储索引

  // 从左向右构建递减栈，存储所有可能的左端点
  for (let i = 0; i < n; i++) {
    if (stack.length === 0 || nums[stack[stack.length - 1]] > nums[i]) {
      stack.push(i)
    }
  }

  let maxWidth = 0

  // 从右向左扫描，找最大宽度
  for (let j = n - 1; j >= 0; j--) {
    while (stack.length > 0 && nums[stack[stack.length - 1]] <= nums[j]) {
      maxWidth = Math.max(maxWidth, j - stack.pop())
    }
  }

  return maxWidth
}

• 时间复杂度：$O(n)$，每个元素最多入栈出栈各一次
• 空间复杂度：$O(n)$，单调栈最坏情况存储所有元素

算法思路：

• 构建递减栈：从左向右遍历，将严格递减的元素索引入栈，这些是所有可能的左端点候选
• 从右向左扫描：遍历数组找右端点，若栈顶元素 ≤ 当前值则可构成坡，弹出栈顶并更新最大宽度
• 贪心原理：栈中元素递减，越靠近栈底值越大索引越小；从右向左扫描保证先遇到更远的右端点